Reste d'une division par 19 - Corrigé

Énoncé

Déterminer le reste de la division euclidienne par $19$ de $1{000}^{1000}$ .

Solution

On écrit la division euclidienne de $1000$ par $19$ :  $\begin{array}{r}1000=19\times 52+12\end{array}$  donc $1000\equiv 12[19]$ , et on a alors $1{000}^{1000}\equiv {12}^{1000}[19]$ .

On remarque que : ${12}^2\equiv 144\equiv 11[19]$ ; ${12}^3\equiv 1728\equiv 18\equiv -1[19]$ .

On écrit la division euclidienne de $1000$ par $3$ :  $\begin{array}{r}1000=3\times 333+1\end{array}$ donc 
$\begin{array}{rl}1{000}^{1000}& \equiv {12}^{1000}\\ & \equiv {12}^{3\times 333+1}\\ & \equiv ({12}^3{)}^{333}\times {12}^1\\ & \equiv (-1{)}^{333}\times 12\\ & \equiv -1\times 12\\ & \equiv -12\equiv 7[19]\end{array}$  

et on en déduit que le reste dans la division euclidienne de $1{000}^{1000}$ par $12$ est $7$ .